#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <vector>

/**
 * Luogu P1103: Arranging Books
 */

struct Book {
    int height;
    int width;

    bool operator<(const Book &other) const { return height < other.height; }
};

int nBooks, nRemove, nKeep;
int buf[101][101];  // f[n, k] means the optima by choose k books from sequence
                    // *ended with* nth element

int main() {
// Input
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d %d", &nBooks, &nRemove);
    std::vector<Book> books;
    for (int i = 0; i < nBooks; i++) {
        int height, width;
        scanf("%d %d", &height, &width);
        books.push_back({height, width});
    }
    std::sort(books.begin(), books.end());

    // Use DP to solve
    nKeep = nBooks - nRemove;
    for (int n = 1; n <= nBooks; n++) buf[n][1] = 0;
    for (int b = 2; b <= nBooks; b++) {
        int maxK = std::min(b, nKeep);
        for (int k = 2; k <= maxK; k++) {
            int min = INT_MAX;
            for (int n = k - 1; n < b; n++) {
                int diff = std::abs(books[n - 1].width - books[b - 1].width);
                int val = buf[n][k - 1] + diff;
                min = std::min(min, val);
            }
            buf[b][k] = min;
        }
    }
    int result = INT_MAX;
    for (int n = nKeep; n <= nBooks; n++)
        result = std::min(result, buf[n][nKeep]);
    printf("%d\n", result);

    return 0;
}
